C/C++ Users Group Library 1996 July/C-C++ Users Group Library July 1996.iso/vol_200/247_01/manual1.doc

Text File | 1989-04-17 | 45KB | 1,651 lines

    M.I.R.A.C.L. - Multiprecision Integer and Rational Arithmetic C Library    _______________________________________________________________________

                                 M. Scott


ABSTRACT:



      A portable C library is described  which  implements  multi-precision

      integer and rational data-types, and provides the routines to perform

      basic  arithmetic  on them.  Certain useful number-theoretic routines

      are also included in the package.



1. INTRODUCTION:



      Conventional computer  arithmetic  facilities  as  provided  by  most

      computer language compilers usually provide one or two floating-point

      data  types  (e.g.  single and double precision) to represent all the

      real numbers,  together with one or more integer types  to  represent

      whole  numbers.  These built-in data-types are closely related to the

      underlying computer architecture,  which is sensibly designed to work

      quickly with large amounts of small numbers,  rather than slowly with

      small amounts of large numbers (given  a  fixed  memory  allocation).

      Floating-point allows a relatively small binary number (e.g. 32 bits)

      to  represent  real numbers to an adequate precision (e.g.  7 decimal

      places) over a large dynamic range.  Integer types allow small  whole

      numbers to be represented directly by their binary equivalent,  or in

      2's complement  form  if  negative.  Nevertheless  this  conventional

      approach to computer arithmetic has several disadvantages.



      (1)   Floating-point  and  Integer  data-types  are  representationly

      incompatible.  Note that the set of integers, although infinite, is a



                                      1






      subset of the rationals (i.e.  fractions),  which is in turn a subset

      of the reals.  Thus every integer has  an  equivalent  floating-point

      representation.  Unfortunately  these  two  representations  will  in

      general be different.  For example a small positive whole number will

      be  represented  by  its  binary  equivalent  as  an integer,  and as

      separated mantissa and exponent as a floating-point. This implies the

      need for conversion routines, to convert from one form to the other.



      (2) Most rational numbers can not be expressed  exactly  (e.g.  1/3).

      Indeed  the  floating-point  system  can  only  express exactly those

      rationals whose denominators are multiples  of  the  factors  of  the

      underlying  radix.  For  example our familiar decimal system can only

      represent exactly  those  rational  numbers  whose  denominators  are

      multiples of 2 and 5; 1/20 is 0.05 exactly, 1/21 is .0476190476190...



      (3) Rounding in floating-point is  base-dependant  and  a  source  of

      obscure errors.



      (4)  The  fact that the size of integer and floating-point data types

      are dictated by the computer architecture,  defeats  the  efforts  of

      language designers to keep their languages portable.



      (5)  Numbers  can  only  be  represented to a fixed machine-dependent

      precision. In many applications this can be a crippling disadvantage,

      for example in the new and growing field of Public-Key cryptography.



      (6) Base-dependent phenomena cannot easily be studied. For example it

      would be difficult to access a particular digit of a decimal  number,

      as  represented  by  a  traditional  integer  data-type.


                                      2








      Herein is described a set of standard  C  routines  which  manipulate

      multi-precision  rational  numbers  directly,   with  multi-precision

      integers as a compatible subset. Approximate real arithmetic can also

      be performed.





2. NUMBER REPRESENTATION



      The two new data-types are called "big" and "flash".  The  former  is

      used  to  store  multiprecision  integers,   and  the  latter  stores

      multiprecision fractions as numerator and denominator  in  "floating-

      slash" form.  Both take the form of a fixed length array of integers,

      with sign and length information encoded in the  first  element,  and

      the  data  itself  in  subsequent  elements.  Both  new  types can be

      introduced into the syntax of the 'C' language by the 'C'  statements

                            typedef int* big;
                            typedef int* flash;

      Now  'big' and 'flash' variables can be declared just like any built-

      in data type, e.g.



                             big x,y[10],z[10][10];



      Note that the user of these data-types is  not  concerned  with  this

      internal representation; the library routines allow "big" and "flash"

      numbers to be manipulated directly.



      The structure of "big" and "flash" numbers is illustrated in figure (1)





                                      3






        x[0]    x[1]   x[2]                x[n]                          x[max]
      ┌─────┐ ┌─────┐ ┌─────┐             ┌─────┐ ┌─────┐                ┌─────┐
      │s 0 n│ │ LSW │ │     │ ..........  │ MSW │ │  0  │ .............. │  0  │
      └─────┘ └─────┘ └─────┘             └─────┘ └─────┘                └─────┘


        x[0]   x[1]    x[2]        x[n]   x[n+1]   x[n+2]     x[n+d]     x[max]
      ┌─────┐ ┌─────┐ ┌─────┐     ┌─────┐ ┌─────┐ ┌─────┐     ┌─────┐    ┌─────┐
      │s d n│ │ LSW │ │     │ ... │ MSW │ │ LSW │ │     │ ... │ MSW │ .. │  0  │
      └─────┘ └─────┘ └─────┘     └─────┘ └─────┘ └─────┘     └─────┘    └─────┘
              <------- numerator ------> / <------ denominator ----->


       Figure (1):  Structure of "big" and "flash" data-types,  where s  is
                   the  sign of the number,  n and d are the lengths of the
                   numerator and denominator respectively,  and LSW and MSW
                   mean  'Least  significant  word'  and  'Most significant
                   word'



      These   structures   combine   ease   of  use  with  representational

      efficiency.  A denominator of length zero (d=0),  implies  an  actual

      denominator  of one;  and similarily a numerator of length zero (n=0)

      implies  a  numerator of one.  Zero itself is uniquely defined as the

      number whose first element is zero (i.e. n=d=0).



      Note that the slash in the  'flash'  data-type  is  not  in  a fixed

      position,    and  may  "float"   depending  on the relative  size  of

      numerator and denominator.



      A "flash" number is manipulated by  splitting  it  up  into  separate

      "big"  numerator  and  denominator  components.  A  "big"  number  is

      manipulated by extracting and operating  on  each  of  its  component

      integer elements.  To avoid possible confusion with the internal sign

      bit,  the  numbers  in each element are limited to a somewhat smaller

      range than that of the full word-length, e.g. 0 to 16383  (= 2^14 -1)

      on a 16-bit micro-computer.





                                      4






      When the system is initialised the user specifies the fixed number of

      words (or bytes) to be assigned to all "big"  or  "flash"  variables,

      and the number base to be used. Any base can be used, up to a maximum

      MAXBASE which is dependant on the wordlength of the computer used. If

      requested  to  use  a  small  base  b,  the system will,  for optimal

      efficiency,  actually use base bⁿ ,  where n is the  largest  integer

      such that bⁿ fits in a single computer word.



      The   encoding  of  the  sign  and  numerator  and  denominator  size